#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

const int MX = 100'000;
bool np[MX + 1];
vector<int> prime_numbers;

int init = []()
{
    np[0] = np[1] = true;
    for (int i = 2; i <= MX; i++)
    {
        if (!np[i])
        {
            prime_numbers.push_back(i);
            for (int j = i; j <= MX / i; j++)
            { 
                np[i * j] = true;
            }
        }
    }
    return 0;
}();

bool is_prime(long long n)
{
    if (n <= MX)
    {
        return !np[n];
    }
    for (long long p : prime_numbers)
    {
        if (p * p > n)
        {
            break;
        }
        if (n % p == 0)
        {
            return false;
        }
    }
    return true;
}

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/sum-of-largest-prime-substrings/solutions/3685356/pan-duan-zhi-shu-pythonjavacgo-by-endles-0w8f/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。